package com.mdnote.practice.binary_tree;

import sun.reflect.generics.tree.Tree;

import java.util.regex.Pattern;

/**
 * @author Rhythm-2019
 * @date 2020/10/1
 * @description 从前序与中序遍历序列构造二叉树
 */
public class LeetCode105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        return _build(0, preorder.length - 1, preorder,
                        0, inorder.length - 1, inorder);
    }

    private TreeNode _build(int preStart, int preEnd, int[] preorder, int inStart, int inEnd, int[] inorder) {
        // Terminator
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        // Process
        // 前需遍历的第一个节点就是根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        // 在中序遍历种找到这个节点
        int inIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
                break;
            }
        }
        // 所以左边字树的大小为
        int leftSize = inIndex - inStart;
        // 构造左右节点
        root.left = _build(preStart + 1, preStart + leftSize, preorder,
                                        inStart, inIndex - 1, inorder);
        root.right = _build(preStart + leftSize + 1, preEnd, preorder,
                                 inIndex + 1, inEnd, inorder);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
